import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class UniformCostSearch implements Search {
	private Graph graph = null;
	private Node node = null;
	private List<Node> visited;			// is for only counting the nodes which are visited, testing purposes

	public Node solve(String start, String end){
		if(graph != null){
			Graph initial = new Graph(graph);
			visited = new ArrayList<Node>();
			Node root = graph.getFirstNode(start);
			List<Node> open = new ArrayList<Node>();
			open.add(root);

			while(!open.isEmpty()){
				Collections.sort(open);
				node = open.remove(0);
				node.setVisited(true);
				visited.add(node);
				if(node.getContent().equals(end)) {
					return node;
				} else {
					List<Node> children = graph.getChildren(node);
					for (Node child : children) {
//						/* Discard nodes already visited */
						if (visited.indexOf(child) == -1) {
							if (open.indexOf(child) != -1) {
								
								/* In case we have a node in open list with greater path cost, replace it with smallest */
								Node newNode = initial.getNodeByName(node.getContent());
								int newCost = 9999999;
								List<Node> neighbors = initial.getNeighbours(newNode);
								
								for (Node neighbor : neighbors) {
									if (neighbor.getContent().equals(child.getContent())) {
										newCost = node.getCost() + neighbor.getCost();
										break;
									}
								}
								
								if(newCost < child.getCost()) {
									child.setCost(newCost);
									child.setParent(node);
								} 
							} else {
								child.setParent(node);
								if (child.getCost() != -1) {
									child.setCost(node.getCost() + graph.getInitCost(child));
								} else {
									child.setCost(node.getCost() + child.getCost());
								}
								
								open.add(child);
							}
						}
						
					}
				}
			}
		}
		
		return node;
	}

	public Graph getGraph() {
		return graph;
	}

	public void setGraph(Graph graph) {
		this.graph = graph;
	}

	public List<Node> getVisited() {
		return visited;
	}

	public void setVisited(List<Node> visited) {
		this.visited = visited;
	}
}
